package com.cd.learn.cdlearn.algorithm;

import com.cd.learn.cdlearn.algorithm.util.CheckAlgorithmUtil;
import org.junit.Test;

/**
 * @Author: seven
 * @Date: 2021/4/29 下午3:42
 * 插入排序
 */
public class InsertSort extends CheckAlgorithmUtil {
    /**
     * 从小到大排序
     * 插入排序：第一次比较，下标为1的和0的比较，比之小则交换，第二次比较，下标为上次开始下标加1,再和自己前面的每一个数进行比较，
     * 因为前面是排好序的，只要遇到比自己小的数就可以停止此次遍历
     */
    @Override
    @Test
    public void test() {
        super.test();
    }

    /**
     * 从第二个数开始循环
     * @param array 将要排序的数组
     */
    @Override
    public void sort(int[] array){
        //从第二个数开始
        for (int i = 1; i < array.length; i++) {
            loop(array,i);
        }
    }

    /**
     * 遍历传参下标，到数组开始位置，比小则交换
     * @param array 数组
     * @param index 开始下标
     */
    public static void loop(int[] array,int index){
        for (int i = index; i > 0; i--) {
            if(array[i] < array[i-1]){
                exchange(array,i,i-1);
            }else {
                //前面是排好序的，遇到比自己还小的就停止循环
               break;
            }
        }
    }





}
